import java.awt.*;

/**
 * 随机选取标定点
 */
public class AlgoVisualizer2 {

    private QuickSortData data;
    private AlgoFrame frame;
    private static int DELAY = 20;

    public AlgoVisualizer2(int sceneWidth, int sceneHeight, int N, QuickSortData.Type dataType) {
        // 初始化数据
        data = new QuickSortData(N, sceneHeight, dataType);

        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("Quick Sort Visualization", sceneWidth, sceneHeight);

            // https://docs.oracle.com/javase/tutorial/uiswing/concurrency/dispatch.html
            // Tasks on the event dispatch thread must finish quickly; if they don't, unhandled events back up and the user interface becomes unresponsive.
            new Thread(this::run).start();
        });
    }

    public AlgoVisualizer2(int sceneWidth, int sceneHeight, int N) {
        this(sceneWidth, sceneHeight, N, QuickSortData.Type.Default);
    }

    // 动画逻辑
    private void run() {
        setData(-1, -1, -1, -1, -1);
        quickSort(0, data.N() - 1);
        setData(-1, -1, -1, -1, -1);
    }

    private void quickSort(int l, int r) {
        if (l > r) {
            return;
        } else if (l == r) {
            setData(l, r, l, -1, -1);
            return;
        }

        setData(l, r, -1, -1, -1);
        int p = partition(l, r);
        quickSort(l, p - 1);
        quickSort(p + 1, r);
    }

    private int partition(int l, int r) {
        // 使用随机位置的元素作为标定点
        int p = (int) (Math.random() * (r - l + 1)) + l;
        setData(l, r, -1, p, -1);

        data.swap(l, p);
        int v = data.get(l);
        setData(l, r, -1, l, -1);

        int j = l;
        // arr[l+1...j] < v; arr[j+1...i] > v
        for (int i = l + 1; i <= r; i ++) {
            setData(l, r, -1, l, i);
            if (data.get(i) < v) {
                j ++;
                data.swap(j, i);
                setData(l, r, -1, l, i);
            }
        }

        data.swap(l, j);
        setData(l, r, j, -1, -1);
        return j;
    }

    private void setData(int l, int r, int fixedPivot, int curPivot, int curElement) {
        data.l = l;
        data.r = r;
        if (fixedPivot != -1) {
            data.fixedPivots[fixedPivot] = true;
        }
        data.curPivot = curPivot;
        data.curElement = curElement;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }

    public static void main(String[] args) {
        int sceneWidth = 800;
        int sceneHeight = 800;
        int N = 100;

//        AlgoVisualizer visualizer = new AlgoVisualizer(sceneWidth, sceneHeight, N);

        // 当数据是近乎有序的时候，算法变成了 O(n^2) 级别的算法。
//        AlgoVisualizer2 visualizer = new AlgoVisualizer2(sceneWidth, sceneHeight, N, QuickSortData.Type.NearlyOrdered);

        // 当数据一样的时候，算法变成了 O(n^2) 级别的算法。
        AlgoVisualizer2 visualizer = new AlgoVisualizer2(sceneWidth, sceneHeight, N, QuickSortData.Type.Identical);
    }
}
